#ifndef _LIST_H_
#define _LIST_H_
#include <atomic>
#include <assert.h>
#include <stdio.h>
#include <iostream>

template <typename T>
struct DListNode {
	DListNode() :prev(nullptr), next(nullptr)  {
	
	}
	DListNode(T& val) :val(val), prev(nullptr), next(nullptr) {
	
	}
	DListNode(T&& val) :val(val), prev(nullptr), next(nullptr)  {

	}
	DListNode(const DListNode&) = delete;
	DListNode& operator=(DListNode&) = delete;
	T val;
	DListNode* prev;
	DListNode* next;
};
template <typename T>
class list {
private:
	class Iterator {
	public:
		Iterator(DListNode<T>* cur) :cur(cur) {
		
		}
		Iterator& operator++() {
			cur = cur->next;
			return *this;
		}
		Iterator& operator++(int) {
			Iterator t = *this;
			++(*this);
			return t;
		}
		Iterator& operator+=(int size) {
			
		}
		T operator*() {
			return cur->val;
		}
	private:
		DListNode<T>* cur;//point current node.
	};
public:
	list() noexcept : head(nullptr), tail(nullptr) {

	}
	~list() {
		destory();
		if (!head && !tail) {
			//printf("class list ---> delete all node success.");
		}
		//std::cout << "~list() - input.size: " << m_size << std::endl;
	}
	void push_front(T& val) {
		push_front(std::move(val));
	}
	void push_front(T&& val) {
		if (!isInit.load()) {	
			Init();
		}
		auto insertNode = new DListNode<T>(val);
		head->next->prev = insertNode;
		insertNode->prev = head;
		insertNode->next = head->next;
		head->next = insertNode;
		++m_size;
	}
	void pop_front() {
		assert(0 < m_size);
		auto popNode = head->next;
		head->next->next->prev = head;
		head->next = head->next->next;
		if (popNode) {
			delete popNode;
			popNode = nullptr;
			--m_size;
		}
	}
	void push_back(T& val) {
		push_back(std::move(val));
	}
	void push_back(T&& val) {
		if (!isInit) {
			Init();
		}
		auto insertNode = new DListNode<T>(val);
		insertNode->prev = tail->prev;
		tail->prev = insertNode;
		insertNode->prev->next = insertNode;
		insertNode->next = tail;
		++m_size;
	}
	void pop_back() {
		assert(0 < m_size);
		auto popNode = tail->prev;
		tail->prev->prev->next = tail;
		tail->prev = tail->prev->prev;
		if (popNode) {
			delete popNode;
			popNode = nullptr;
			--m_size;
		}
	}
	size_t size()const {
		return m_size;
	}
	bool empty()const {
		return m_size > 0;
	}
	T front() const {
		assert(0 < m_size);
		return head->next->val;
	}
	T back() const {
		assert(0 < m_size);
		return tail->prev->val;
	}
	template <class ...Args>
	void emplace_back(Args &&...args) {
		push_back(std::forward<Args>(args)...);
	}
	template <class ...Args>
	void emplace_front(Args &&...args) {
		push_front(std::forward<Args>(args)...);
	}
	void merge(list<T>& right) {
		merge(std::move(right));
	}
	void merge(list<T>&& right) {
		bool res = issort();
		assert(res);
		/*for (int i = 0; i < right.size(); ++i) {
			this->push_back(right[i]);
		}*/
	}
	Iterator begin() {
		assert(0 < m_size);
		return Iterator{ head->next };
	}
	//only test.
	T& operator[](int index) {
		assert(0 <= index && index < m_size);
		assert(head && tail);
		auto p = head->next;
		size_t i = 0;
		while (i <= index) {
			if (i == index) return p->val;
			p = p->next;
			++i;
		}
	}
private:
	bool Init() {
		if (!head && !tail) {
			head = new DListNode<T>();
			tail = new DListNode<T>();
			tail->prev = head;
			head->next = tail;
			isInit.store(true);
		}
		return isInit;
	}
	bool issort() {
		if (m_size == 0 || m_size == 1) {
			return true;
		}
		auto pre = head->next, p = head->next->next;
		while (p != tail) {
			if (pre->val > p->val) return false;
			pre = p;
			p = p->next;
		}
		return true;
	}
	void destory() {
		if (m_size > 0) {
			auto p = head->next;
			while (p != tail) {
				auto deleteNode = p;
				p = p->next;
				p->prev = head;
				head->next = p;
				if (deleteNode) {
					delete deleteNode;
					deleteNode = nullptr;
					--m_size;
				}
			}
		}
		if (head && tail) {
			delete head;
			head = nullptr;
			delete tail;
			tail = nullptr;
		}
	}
private:
	DListNode<T>* head;
	DListNode<T>* tail;
	std::atomic_bool isInit = false;
	size_t m_size = 0;
};
#endif _LIST_H_